//给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 
//
// 示例: 
//
// 输入: 3
//输出: 5
//解释:
//给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
//
//   1         3     3      2      1
//    \       /     /      / \      \
//     3     2     1      1   3      2
//    /     /       \                 \
//   2     1         2                 3 
// Related Topics 树 动态规划 
// 👍 700 👎 0

package leetcode.editor.cn;

//leetcode submit region begin(Prohibit modification and deletion)
class P96UniqueBinarySearchTrees {
	public int numTrees(int n) {
		/**
		 *  n的范围 根节点的取值范围是 i{1,2,3..............n}
		 *  左节点个数 取值范围  j {0,i-1};
		 *  右节点个数 取值范围 k {i-1-j};
		 *  个数的话 f(n)=sum(f(j)*f(i-1-j))
		 */

		int[] dp = new int[n + 1];
		dp[0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= i - 1; j++) {
				dp[i] += dp[j] * dp[i - 1 - j];
			}
		}

		return dp[n];
	}
}
//leetcode submit region end(Prohibit modification and deletion)
